package com.fengkai.filepost.pdfoutstream.test.ODsolutions;

import java.util.Collections;
import java.util.LinkedList;

/**
 * @author Fengkai
 * @creat 2023/4/14
 * 一次执行 2n 个指令往队列中添加数据和移除数据，
 * 其中 n 个指令是添加数据(可能从头部也可以从尾部添加)
 * 依次添加 1 到 n , n 个指令是移出数据
 * 现在要求移除数据的顺序为 1 到 n ，
 * 为了满足最后输出的要求,
 * 小 A 可以在任何时候调整队列中的数据的顺序
 * 请问,小 A 最少需要调整几次才能满足移除数据的顺序正好是 1 到 n
 * 输入
 * 第一行一个整数 n ，表示数据范围
 * 接下来有 2n 行,其中有 n 行为添加数据:
 * 指令head add x表示从头部添加数据x
 * tail add x表示从尾部添加数据x
 * 另外 n 行为移除数据指令,指令为remove形式,表示移除一个数据
 * 1≤n≤3×1 0 5 10^510
 * 5
 * 输出描述
 * 一个整数，表示小 A 要调整的最小次数
 */
public class SpecisalLinkedList {
    public static void main (String[] args) {
        System.out.println(sortPol(3, new String[]{"tail add 1","head add 2", "remove",  "head add 3", "remove", "remove"}));
    }

    public static int sortPol (int n, String[] insts) {
        LinkedList<Integer> integers = new LinkedList<>();
        int count = 0;
        int index = 1;
        for (String inst : insts) {
            char c = inst.charAt(0);
            switch (c) {
                case 'h':
                    integers.addFirst(Integer.parseInt(inst.split(" ")[2]));
                    break;
                case 't':
                    integers.addLast(Integer.parseInt(inst.split(" ")[2]));
                    break;
                default:
                    if (!integers.getFirst().equals(index ++)) {
                        Collections.sort(integers);
                        count ++;
                    }
                    integers.removeFirst();
                    break;
            }
        }
        return count;
    }
}
